

<!DOCTYPE html>
<html lang="en" color-mode=light>
<head>
  <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>树状数组 - Alex</title>
  <meta name="apple-mobile-web-app-capable" content="yes" />
  <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
  <meta name="google" content="notranslate" />
  
  <meta name="description" content="维护前缀和的方式，在需要多次更新前缀和时比普通数组高效...">
  <meta name="author" content="Alex">
  <link rel="icon" href="/images/icons/favicon-16x16.png" type="image/png" sizes="16x16">
  <link rel="icon" href="/images/icons/favicon-32x32.png" type="image/png" sizes="32x32">
  <link rel="apple-touch-icon" href="/images/icons/apple-touch-icon.png" sizes="180x180">
  <meta rel="mask-icon" href="/images/icons/stun-logo.svg" color="#333333">
  
    <meta rel="msapplication-TileImage" content="/images/icons/favicon-144x144.png">
    <meta rel="msapplication-TileColor" content="#000000">
  

  
<link rel="stylesheet" href="/css/style.css">


  
    
<link rel="stylesheet" href="//at.alicdn.com/t/font_1445822_s6x2xcokxrl.css">

  

  
    
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/fancybox/3.5.7/jquery.fancybox.min.css">

  

  
    
      
        
        
<link rel="stylesheet" href="https://cdn.bootcss.com/highlight.js/9.18.1/styles/xcode.min.css" name="highlight-style" mode="light">

      
        
        
<link rel="stylesheet" href="https://cdn.bootcss.com/highlight.js/9.18.1/styles/solarized-dark.min.css" name="highlight-style" mode="dark">

      
  

  <script>
    var CONFIG = window.CONFIG || {};
    var ZHAOO = window.ZHAOO || {};
    CONFIG = {
      isHome: false,
      fancybox: true,
      pjax: false,
      lazyload: {
        enable: true,
        only_post: 'false',
        loading: '/images/theme/loading.gif'
      },
      donate: {
        enable: true,
        alipay: 'https://pic.izhaoo.com/alipay.jpg',
        wechat: 'https://pic.izhaoo.com/wechat.jpg'
      },
      galleries: {
        enable: true
      },
      fab: {
        enable: true,
        always_show: false
      },
      carrier: {
        enable: true
      },
      daovoice: {
        enable: false
      },
      preview: {
        background: {
          default: '/images/theme/welcome-image.jpg',
          api: ''
        },
        motto: {
          default: '我在开了灯的床头下，想问问自己的心啊。',
          api: 'https://v2.jinrishici.com/one.json',
          data_contents: '["data","content"]'
        },
      },
      qrcode: {
        enable: true,
        type: 'url',
        image: 'https://pic.izhaoo.com/weapp-code.jpg',
      },
      toc: {
        enable: true
      },
      scrollbar: {
        model: 'simple'
      },
      notification: {
        enable: false,
        delay: 4500,
        list: '',
        page_white_list: '',
        page_black_list: ''
      }
    }
  </script>

  

  

<meta name="generator" content="Hexo 5.1.1"></head>

<body class="lock-screen">
  <div class="loading"></div>
  


  <nav class="navbar">
    <div class="left">
      
        <i class="iconfont iconqrcode j-navbar-qrcode"></i>
      
      
        <i class="iconfont iconmoono" id="color-toggle" color-toggle="light"></i>
      
    </div>
    <div class="center">树状数组</div>
    <div class="right">
      <i class="iconfont iconmenu j-navbar-menu"></i>
    </div>
    
      <div id="qrcode-navbar"></div>
    
  </nav>

  

<nav class="menu">
  <div class="menu-wrap">
    <div class="menu-close">
      <i class="iconfont iconbaseline-close-px"></i>
    </div>
    <ul class="menu-content"><li class="menu-item">
        <a href="/ " class="underline "> 首页</a>
      </li><li class="menu-item">
        <a href="/galleries/ " class="underline "> 摄影</a>
      </li><li class="menu-item">
        <a href="/archives/ " class="underline "> 归档</a>
      </li><li class="menu-item">
        <a href="/tags/ " class="underline "> 标签</a>
      </li><li class="menu-item">
        <a href="/categories/ " class="underline "> 分类</a>
      </li><li class="menu-item">
        <a href="/about/ " class="underline "> 关于</a>
      </li></ul>
    
      <div class="menu-copyright"><p>Powered by <a target="_blank" href="https://hexo.io">Hexo</a>  |  Theme - <a target="_blank" href="https://github.com/izhaoo/hexo-theme-zhaoo">zhaoo</a></p></div>
    
  </div>
</nav>
  <main id="main">
  <div class="article-wrap">
    <div class="row container">
      <div class="col-xl-3"></div>
      <div class="col-xl-6"><article class="article">
  <div class="wrap">
    <section class="head">
  <img   class="lazyload" data-original="/images/theme/post-image.jpg" src=""  draggable="false">
  <div class="head-mask">
    <h1 class="head-title">树状数组</h1>
    <div class="head-info">
      <span class="post-info-item"><i class="iconfont iconcalendar"></i>June 17, 2021</span>
      
      <span class="post-info-item"><i class="iconfont iconfont-size"></i>427</span>
    </div>
  </div>
</section>
    <section class="main">
      <section class="content">
        <h2 id="1-什么是树状数组？"><a href="#1-什么是树状数组？" class="headerlink" title="1.什么是树状数组？"></a>1.什么是树状数组？</h2><p>顾名思义，就是用数组来模拟树形结构呗。那么衍生出一个问题，为什么不直接建树？答案是没必要，因为树状数组能处理的问题就没必要建树。和Trie树的构造方式有类似之处。</p>
<h2 id="2-树状数组可以解决什么问题"><a href="#2-树状数组可以解决什么问题" class="headerlink" title="2.树状数组可以解决什么问题"></a>2.树状数组可以解决什么问题</h2><p>可以解决大部分基于区间上的更新以及求和问题。</p>
<h2 id="3-树状数组和线段树的区别在哪里"><a href="#3-树状数组和线段树的区别在哪里" class="headerlink" title="3.树状数组和线段树的区别在哪里"></a>3.树状数组和线段树的区别在哪里</h2><p>树状数组可以解决的问题都可以用线段树解决，这两者的区别在哪里呢？树状数组的系数要少很多，就比如字符串模拟大数可以解决大数问题，也可以解决1+1的问题，但没人会在1+1的问题上用大数模拟。</p>
<h2 id="4-树状数组的优点和缺点"><a href="#4-树状数组的优点和缺点" class="headerlink" title="4.树状数组的优点和缺点"></a>4.树状数组的优点和缺点</h2><p>修改和查询的复杂度都是O(logN)，而且相比线段树系数要少很多，比传统数组要快，而且容易写。</p>
<p>缺点是遇到复杂的区间问题还是不能解决，功能还是有限。</p>
<blockquote>
<p>详见：</p>
<p><a target="_blank" rel="noopener" href="https://www.cnblogs.com/xenny/p/9739600.html">https://www.cnblogs.com/xenny/p/9739600.html</a></p>
</blockquote>
      </section>
      <section class="extra">
        
          <ul class="copyright">
  
    <li><strong>本文作者：</strong>Alex</li>
    <li><strong>本文链接：</strong><a href="https://alexande.gitee.io/2021/06/17/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84/index.html" title="https:&#x2F;&#x2F;alexande.gitee.io&#x2F;2021&#x2F;06&#x2F;17&#x2F;%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84&#x2F;index.html">https:&#x2F;&#x2F;alexande.gitee.io&#x2F;2021&#x2F;06&#x2F;17&#x2F;%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84&#x2F;index.html</a></li>
    <li><strong>版权声明：</strong>本博客所有文章均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" title="BY-NC-SA" target="_blank" rel="noopener">BY-NC-SA</a> 许可协议，转载请注明出处！</li>
  
</ul>
        
        
          <section class="donate">
  <div id="qrcode-donate">
    <img   class="lazyload" data-original="https://pic.izhaoo.com/alipay.jpg" src="" >
  </div>
  <div class="icon">
    <a href="javascript:;" id="alipay"><i class="iconfont iconalipay"></i></a>
    <a href="javascript:;" id="wechat"><i class="iconfont iconwechat-fill"></i></a>
  </div>
</section>
        
        
  <ul class="tag-list" itemprop="keywords"><li class="tag-list-item"><a class="tag-list-link" href="/tags/%E5%89%8D%E7%BC%80%E5%92%8C/" rel="tag">前缀和</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" rel="tag">数据结构</a></li></ul> 

        
  <nav class="nav">
    <a href="/2021/08/05/dom%E5%B1%82%E7%BA%A7%E9%A1%BA%E5%BA%8F/"><i class="iconfont iconleft"></i>dom层级顺序</a>
    <a href="/2021/05/19/css-%E5%9D%97%E7%BA%A7%E8%A1%8C%E5%86%85%E5%85%83%E7%B4%A0/">css-块级行内元素<i class="iconfont iconright"></i></a>
  </nav>

      </section>
      
    </section>
  </div>
</article></div>
      <div class="col-xl-3">
        
          
  <aside class="toc-wrap">
    <h3 class="toc-title">文章目录：</h3>
    <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#1-%E4%BB%80%E4%B9%88%E6%98%AF%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84%EF%BC%9F"><span class="toc-text">1.什么是树状数组？</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84%E5%8F%AF%E4%BB%A5%E8%A7%A3%E5%86%B3%E4%BB%80%E4%B9%88%E9%97%AE%E9%A2%98"><span class="toc-text">2.树状数组可以解决什么问题</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#3-%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84%E5%92%8C%E7%BA%BF%E6%AE%B5%E6%A0%91%E7%9A%84%E5%8C%BA%E5%88%AB%E5%9C%A8%E5%93%AA%E9%87%8C"><span class="toc-text">3.树状数组和线段树的区别在哪里</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#4-%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84%E7%9A%84%E4%BC%98%E7%82%B9%E5%92%8C%E7%BC%BA%E7%82%B9"><span class="toc-text">4.树状数组的优点和缺点</span></a></li></ol>
  </aside>

        
      </div>
    </div>
  </div>
</main>
  

<footer class="footer">
  <div class="footer-social"><a 
        href="tencent://message/?Menu=yes&uin=272991962 "
        target="_blank"
        class="footer-social-item"
        onMouseOver="this.style.color= '#12B7F5'" 
        onMouseOut="this.style.color='#33333D'">
          <i class="iconfont  iconQQ "></i>
      </a><a 
        href="https://github.com/zheng-kai "
        target="_blank"
        class="footer-social-item"
        onMouseOver="this.style.color= '#9f7be1'" 
        onMouseOut="this.style.color='#33333D'">
          <i class="iconfont  icongithub-fill "></i>
      </a><a 
        href="https://gitee.com/AlexAnde "
        target="_blank"
        class="footer-social-item"
        onMouseOver="this.style.color= '#9f7be1'" 
        onMouseOut="this.style.color='#33333D'">
          <i class="iconfont  gitee-fill-round "></i>
      </a><a 
        href="mailto:272991962@qq.com "
        target="_blank"
        class="footer-social-item"
        onMouseOver="this.style.color=  '#12B7F5'" 
        onMouseOut="this.style.color='#33333D'">
          <i class="iconfont  iconmail "></i>
      </a></div>
  
    <div class="footer-copyright"><p>Powered by <a target="_blank" href="https://hexo.io">Hexo</a>  |  Theme - <a target="_blank" href="https://github.com/izhaoo/hexo-theme-zhaoo">zhaoo</a></p></div>
  
</footer>
  
      <div class="fab fab-plus">
    <i class="iconfont iconplus"></i>
  </div>
  
  
  <div class="fab fab-up">
    <i class="iconfont iconcaret-up"></i>
  </div>
  
  
    <div class="scrollbar j-scrollbar">
  <div class="scrollbar-current j-scrollbar-current"></div>
</div>
  
  
    
<script src="/js/color-mode.js"></script>

  
</body>

<script src="https://cdn.bootcss.com/jquery/3.4.1/jquery.min.js"></script>



  
<script src="https://cdn.bootcdn.net/ajax/libs/jquery.lazyload/1.9.1/jquery.lazyload.min.js"></script>




  
<script src="https://cdnjs.cloudflare.com/ajax/libs/fancybox/3.5.7/jquery.fancybox.min.js"></script>






  
<script src="https://cdn.bootcdn.net/ajax/libs/jquery.qrcode/1.0/jquery.qrcode.min.js"></script>




<script src="/js/utils.js"></script>
<script src="/js/script.js"></script>





  <script>
    (function () {
      var bp = document.createElement('script');
      var curProtocol = window.location.protocol.split(':')[0];
      if (curProtocol === 'https') {
        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
      } else {
        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
      }
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(bp, s);
    })();
  </script>













</html>